package com.test.daily.leetcode.y2022.m07.day0707.v03;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/12 下午 03:04
 * @version: 1.0
 */
public class Solution {
    public static int process(int[] arr, int left, int right) {
        int mid = left + ((right - left) >> 1);
        return process(arr, left, mid)
                + process(arr, mid + 1, right)
                + merge(arr, left, mid, right);
    }

    public static int merge(int[] arr, int left, int mid, int right) {

        int[] help = new int[right - left + 1];
        int p1 = left, p2 = mid + 1;
        int i = 0;
        int ans = 0;
        int windowR = mid + 1;
        int windowL = left;
        for(;windowL <= mid; windowL++){
            while(windowR <= right && arr[windowL] > arr[windowR]*2){
                windowR++;
            }
            ans += windowR - windowL;
        }
        while(p1 <= mid && p2 <= right){
            help[i++] = arr[p1] < arr[p2] ? arr[p1++]: arr[p2++];
        }
        while(p1<=mid){
            help[i++] = arr[p1++];
        }
        while(p2<=right){
            help[i++] = arr[p2++];
        }
        i = 0;
        for(;i < help.length; i++){
            arr[left + i] = help[i];
        }
        return ans;
    }
}
